// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2003 University of Colorado
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: patricia.h,v 1.11 2010-03-11 15:16:40 carzanig Exp $
//
#ifndef PATRICIA_H
#define PATRICIA_H

#ifdef WITH_PATRICIA_PRINT
#include <iostream>
#include <iomanip>
#endif
#include "siena/allocator.h"

using namespace std;

namespace siena {

/*  The structure implements a PATRICIA trie, as described in
 *  R.Sedgewick "Algorithms in C" 3rd Ed., pp. 623--627.  In practice,
 *  this implementation is quite different from the one given by
 *  Sedgewick.  In particular, it is not recursive, and it uses a
 *  combined search/insert method that is identical to the [] operator
 *  in std::map.  Another variation I introduced is that this
 *  structure uses a mask instead of a bit position, which should be
 *  more efficient (although I have not tested that.)
 *
 *  This data structure, implemented here as a template, is intended
 *  to be used within the matching algorithm as a super-efficient
 *  random-access map between filter identifiers and counters
 *  (unsigned short).  For maximum control, I use my own allocator.
 */
template <class T>
class patricia_map {
public:
	patricia_map() throw() {
		root = new (mem) node(0, 0);
	}

	explicit patricia_map(FTAllocator &master_alloc) throw() {
		master_alloc.attach_sub_allocator (mem);
		root = new (mem) node(0, 0);
	}

	~patricia_map() throw() {
		mem.clear();
	}

	typedef unsigned int key_t;

	T & operator[] (register key_t key) throw() {
		register key_t mask;
		register node * n = root;

		do {
			mask = n->mask;
			n = ((key & mask) == 0) ? n->left : n->right;
		} while (n->mask > mask);

		if (n->key == key) return n->count;

		for(mask = 1; (n->key & mask) == (key & mask); mask <<= 1);

		register node ** target = &(root->left);
		n = root;
		while ((*target)->mask < mask && (*target)->mask > n->mask) {
			n = *target;
			target = ((key & n->mask) == 0) ? &(n->left) : &(n->right);
		}
		n = *target;
		register node * x = new (mem) node(key, mask);
		*target = x;
		if ((key & mask) == 0)
			x->right = n;
		else
			x->left = n;

		return x->count;
	}

#ifdef WITH_PATRICIA_PRINT
	void print() const {
		print(root, 0);
	};
#endif

private:
	struct node {
		// Each of the children is valid iff its mask is < this node's mask.
		// So, using a pointer to the node itself for "left" and "right"
		// is effectively making both children invalid.
		node(key_t k, key_t m) throw()
	    		: key(k), mask(m), left(this), right(this), count() {};
		key_t key;
		key_t mask;
		node * left;
		node * right;
		T count;
	};

	FTAllocator mem;
	node * root;

#ifdef WITH_PATRICIA_PRINT
	static void print(const node * n, int l) {
		cout << setw(2) << setfill('0') << hex << n->key << '/' << setw(2) << hex << n->mask;
		if (n->mask < n->left->mask) {
			cout << "-->";
			print(n->left, l + 1);
		} else {
			cout << "--|" << setw(2) << setfill('0') << hex << n->left->key << endl;
		}
		for(int i = 0; i < l; ++i) cout << "  |     ";
		if (n->mask < n->right->mask) {
			cout << "  v" << endl;
			for(int i = 0; i < l; ++i) cout << "  |     ";
			print(n->right, l);
		} else {
			cout << "  -" << endl;
			for(int i = 0; i < l; ++i) cout << "  |     ";
			cout << " " << setw(2) << setfill('0') << hex << n->right->key << endl;
		}
	}
#endif
};

} // end namespace siena

#endif
